CSCI 0014. Data Structures
Units: 3
Prerequisite: Completion of CSCI 66 with grade of "C" or better; and completion with grade of "C" or better, or concurrent enrollment in CSCI 26
Advisory: Completion of CSCI 13 with grade of "C" or better
Hours: 72 (54 lecture, 18 laboratory)
A comprehensive introduction of data structures for computer science. Topics include: lists, stacks, trees, hash tables, and heaps. Associated algorithms are also covered: searching, sorting, traversal, path finding, spanning tree, and network flow. C++ is used as the implementation language. (CSU, UC)
CSCI 0014 - Data Structures
http://catalog.sierracollege.edu/course-outlines/csci-0014/
Catalog Description DESCRIPTION IS HERE: Prerequisite: Completion of CSCI 66 with grade of "C" or better; and completion with grade of "C" or better, or concurrent enrollment in CSCI 26 Advisory: Completion of CSCI 13 with grade of "C" or better Hours: 72 (54 lecture, 18 laboratory) Description: A comprehensive introduction of data structures for computer science. Topics include: lists, stacks, trees, hash tables, and heaps. Associated algorithms are also covered: searching, sorting, traversal, path finding, spanning tree, and network flow. C++ is used as the implementation language. (CSU, UC) Units 3 Lecture-Discussion 54 Laboratory 18 By Arrangement Contact Hours 72 Outside of Class Hours Course Student Learning Outcomes Apply algorithm analysis to the operations on data structures and interpret the results. Describe and evaluate the operations and possible implementations of abstract data types for lists and trees. Describe the operation and characteristics of sorting algorithms. Describe the operation and application of graph algorithms. Select and justify appropriate data structures and algorithms for complex programming tasks. Course Content Outline I. Overview of data structures A. Abstract data types (ADT) B. Measuring complexity and efficiency 1. Computation time 2. Storage needs 3. Problem space 4. Big-O II. Lists A. Single-linked list B. Doubly-linked list C. Stack D. Queue III. Trees A. Binary tree B. Binary search tree C. Heap D. B-Tree E. AVL Tree F. Red-black tree G. Splay tree H. Tries I. Huffman encoding IV. Hashing A. Hash functions B. Hash table C. File-based hash table V. Graphs A. Directed acyclic graph (DAG) B. Cyclic graph C. Sets D. Algorithms: depth-first search, breadth-first search, shortest path, topological sort, network flow, minimum spanning tree VI. Algorithms A. Sorting: insertion sort, bubble sort, shell sort, merge sort, quicksort, heap sort, radix sort, bucket sort BP vs. NP Course Objectives Course Objectives Lecture Objectives: 1. Describe the structure and operations on the following abstract data types: lists, stacks, queues, binary trees, AVL trees, splay trees, tries, B-trees, hash tables, and heaps; 2. Describe the operation of the following sorting algorithms: insertion sort, shell sort, heapsort, mergesort, quicksort, bucket sort, and radix sort; 3. Describe the operation and application of the following graph algorithms: depth first search, breadth first search, shortest path, minimum spanning tree, network flow, and topological sort; 4. Analyze the time and space complexity of the above data structures and algorithms using Big-O notation; 5. Analyze a problem specification to select appropriate data structures and algorithms; and 6. Describe the BP vs. NP problem and its implications. Laboratory Objectives: 1. Write programs that implement the above data structures and algorithms; 2. Test the implementations to verify time and space complexity; 3. Write source code that is easy to read, well organized, well commented; and 4. Employ debugging techniques to assist in programming. Methods of Evaluation Essay Examinations Objective Examinations Problem Solving Examinations Projects Reading Assignments 1. Read the sections from the textbook about hash tables. Pay particular attention to the hash function, its domain of inputs, and range of outputs. Identify the application of a hash table. Be prepared to discuss in class. 2. Consult the Standard Template Library documentation for the built-in implementation of the singly-linked list. Determine the class name, constructor, and methods to add and remove elements from the list. Be prepared to discuss in class. Writing, Problem Solving or Performance Laboratory assignment per week solving problems with different data structure discussed in class 1. Apply the hash function shown in the textbook to the inputs "hello", "hola", and "bonjour". What are the outputs of the hash function for each input? Construct a table on paper showing the inputs and corresponding outputs. Come up with at least three of your own inputs and show the corresponding outputs. Are there any duplicate outputs? 2. Determine the Big-O running time of inserting an element into a random location of a singly-linked list. Express the answer in terms of the number of elements already in the list. 3. Draw a picture of a red-black tree with at least ten elements in it. A new element will be inserted somewhere in the middle of the tree. Show the intermediate steps (with a new drawing for each) as the tree is re-balanced. Draw a picture of the final tree, which must also be balanced. Other (Term projects, research papers, portfolios, etc.) Methods of Instruction Laboratory Lecture/Discussion Distance Learning Other materials and-or supplies required of students that contribute to the cost of the course.
Course Identification Numbering System (C-ID)
...COMP 122 CSCI 0012 COMP 132 CSCI 0013...0010B THTR 171 THEA 0014 THTR 173 THEA...
